package com.hackerank.warmup;

import java.util.HashMap;
import java.util.Map;
/**
 * Sock Merchant
 * https://www.hackerrank.com/challenges/sock-merchant/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=warmup
 *
 * 题目大意：
 * 1、输入n，接下来输入长度为n的数组
 * 2、数组中相同的数代表相同颜色的袜子，两支相同颜色袜子能够组成一双袜子
 * 3、输出最多能组成几双袜子
 *
 * 解题思路：
 * 1、map中key存放数字（颜色），value存放当前是奇数还是偶数
 * 2、遇到相同数字（颜色），从map中取value，如果能组成偶数，则双数加一
 *
 * 时间复杂度O(n)，空间复杂度O(n)
 * **/
public class SockMerchant {
    // Complete the sockMerchant function below.
    static int sockMerchant(int n, int[] ar) {
        int pair = 0;
        Map<Integer,Boolean> pairMap = new HashMap();
        for(int i=0;i<n;i++){
            Boolean flag = pairMap.get(ar[i]);
            flag = (flag == null ? false : !flag);
            pairMap.put(ar[i],flag);
            pair += (flag ? 1:0);
        }
        return pair;
    }
}
